package 每日一题;

import publicClass.TreeNode;

/**
 * 1026. 节点与其祖先之间的最大差值
 * 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
 * <p>
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
 * 输出：7
 * 解释：
 * 我们有大量的节点与其祖先的差值，其中一些如下：
 * |8 - 3| = 5
 * |3 - 7| = 4
 * |8 - 1| = 7
 * |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [1,null,2,null,0,3]
 * 输出：3
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中的节点数在 2 到 5000 之间。
 * 0 <= Node.val <= 105
 * 通过次数26,460提交次数35,799
 */
public class D230418_T1026 {
    //使用深度递归 方法参数 传入祖先节点的最大值 和最小值
    public int maxAncestorDiff(TreeNode root) {

        //根节点没有祖父节点 无法计算差值
        return Math.max(dfsFindMaxAbs(root.right, root.val, root.val), dfsFindMaxAbs(root.left, root.val, root.val));

    }

    /**
     * 递归 计算当前节点及其子节点与祖父节点的最大值
     *
     * @param node             当前节点
     * @param maxFatherNodeVal 祖父节点的最大值
     * @param minFatherNodeVal 祖父节点的最小值
     * @return 与祖父节点的最大差值
     */
    public int dfsFindMaxAbs(TreeNode node, int maxFatherNodeVal, int minFatherNodeVal) {

        int res;

        if (node == null) {
            return 0;
        }
        //算出与祖父节点的最大差值
        res = Math.max(Math.abs(node.val - maxFatherNodeVal), Math.abs(node.val - minFatherNodeVal));

        //递归算出 子节点与祖父节点的最大差值
        int leftMaxAbsVal = 0;
        if (node.left != null) {
            leftMaxAbsVal = dfsFindMaxAbs(node.left, Math.max(maxFatherNodeVal, node.val), Math.min(minFatherNodeVal, node.val));
        }
        int rightMaxAbsVal = 0;
        if (node.right != null) {
            rightMaxAbsVal = dfsFindMaxAbs(node.right, Math.max(maxFatherNodeVal, node.val), Math.min(minFatherNodeVal, node.val));
        }
        //返回当前节点,左子节点,右子节点 中 与祖父节点的最大差值
        return Math.max(res, Math.max(leftMaxAbsVal, rightMaxAbsVal));
    }

}
